import java.util.*;

public class Day12 {

    //求最小的k个数
    int[] nums;
    int q;
    public int[] inventoryManagement(int[] stock, int cnt) {
        //求最小的k个数

        nums = new int[cnt];
        if(cnt==0) return nums;
        if(cnt==stock.length) return stock;
        qsort(stock,0,stock.length-1,cnt);
        return nums;
    }
    public void qsort(int[] a,int start,int end,int k) {
        if(start >= end) {
            nums[q++]=a[start];
            return;
        }
        //int key = a[start];
        int key = a[new Random().nextInt(end-start+1)+start];
        int left=start-1,right=end+1,i=start;
        int[] c = {0,0,0};
        while(i<right) {
            if(a[i] < key) {
                swap(a,++left,i++);
                c[0]++;
            }else if(a[i]==key) {
                i++;
                c[1]++;
            }else {
                swap(a,--right,i);
                c[2]++;
            }
        }
        if(c[0]>k) {
            qsort(a,start,left,k);
        }else if(c[0]+c[1]>=k) {
            int j=start;
            int s=k;
            while(k!=0) {
                nums[q++]=a[j++];
                k--;
            }
        }else {
            for(int j=start;j<right;j++) {
                nums[q++]=a[j];
            }
            qsort(a,right,end,k-c[0]-c[1]);
        }
    }
    public void swap(int[] a,int i,int j) {
        int tmp=a[i];
        a[i]=a[j];
        a[j]=tmp;
    }
}
